#include <stdio.h>/*该文件包含printf()等函数*/
#include <stdlib.h>/*该文件包含exit()等函数*/
#include <malloc.h>/*该文件包含malloc()等函数*/

typedef int DataType;/*定义DataType为int*/


typedef struct Node
{
  DataType data;
  struct Node *next;
} LNode;

/*单链表初始化。初始化成功函数返回0，否则返回1。*/
int ListInitiate(LNode **head){
    *head=(LNode *)malloc(sizeof(LNode));        //分配一个头结点
    if (*head == NULL)                                //内存不足分配失败
        return 1;
    (*head) ->next  = NULL;
    return 0;
}

/* 函数返回由head所表示的单链表的长度。*/
int ListLength(LNode *head) {
    LNode *p = head;//P指向头结点
    int size = 0;//size初始为0

    while (p->next != NULL)//循环计数
    {
        p = p->next;
        size++;
    }
    return size;
}
// 在由head所表示的单链表里插入一个元素 x 到位置 i。
// 插入成功函数返回0，否则返回1。
int ListInsert(LNode *head, int i, DataType x){
    LNode *p,*q;
    int j;

    p=head;
    j=-1;
    while(p->next != NULL&&j<i-1)
        //最终让指针P指向第i-1个结点
    {
        p=p->next;
        j++;
    }

    if(j!=i-1)
    {
        printf("插入元素位置参数错！");
        return 0;
    }

    q=(LNode *)malloc(sizeof(LNode));//生成新结点
    q->data=x;//新结点数据域赋值

    q->next=p->next;
    p->next=q;
    return 1;
}


// 在由head所表示的单链表里删除位置 i 上的元素并将其值存入 x 变量里。调用成功后，列表长度减1。
int ListDelete(LNode *head, int i, DataType *x){
    LNode *p,*s;
    int j;
    p=head;
    j=-1;
    while(p->next!=NULL&&p->next->next!=NULL&&j<i-1)
        //循环结束时指针P指向第i-1个结点
    {
        p=p->next;
        j++;
    }

    if(j!=i-1)
    {
        printf("删除数据元素位置参数错！");
        return 0;
    }

    s=p->next;//指针S指向ai结点
    *x=s->data;//把指针s所指结点的数据域值赋予x
    p->next=p->next->next;//删除
    free(s);//释放指针s所指结点的内存空间
    return 1;
}

// 在由head所表示的单链表里获取位置 i 上的元素并将其值存入 x 变量里。调用成功后，列表长度不变。
int ListGet(LNode *head, int i, DataType *x){
    LNode *p;
    int j;

    p=head;
    j=-1;
    while(p->next!=NULL&&j<i)
    {
        p=p->next;
        j++;
    }

    if(j!=i)
    {
        printf("取元素位置参数错！");
        return 0;
    }

    *x=p->data;
    return 1;
}

// 释放所有的由head所表示的单链表里的元素节点（含头结点）。当释放完全成功时，函数返回0，否则返回1。
int Destroy(LNode **head){
    LNode *p,*p1;

    p=*head;
    while(p!=NULL)
    {
        p1=p;
        p=p->next;
        free(p1);
    }
    *head=NULL;
}

